package search.backtracking;

/**
 * @Classname : JumpGame
 * @Description : 55. 跳跃游戏
 * https://leetcode.cn/problems/jump-game/
 * @Author : chentianyu
 * @Date 2023/3/18 23:30
 */


public class JumpGame {
    public boolean canJump(int[] nums) {
        // 0：初始状态；1：true；-1：false
        int[] memory = new int[nums.length];
        return backTracking(nums, 0, memory);
    }

    private boolean backTracking(int[] nums, int p, int[] memory) {
        if (p == nums.length - 1) return true;
        if (p >= nums.length) return false;
        if (memory[p] != 0) return memory[p] == 1;

        for (int i = nums[p]; i > 0; i--) {
            if (backTracking(nums, p + i, memory)) {
                memory[p] = 1;
                return true;
            }
        }
        memory[p] = -1;
        return false;
    }
}
